【题解】洛谷P10572 - [JRKSJ R8] +1-1

解题思路

先考虑几个必要条件：

• \(x\) 结点是 ( 且 \(y\) 结点是 )。
• \(x\) 到 \(y\) 至少有一条路径经过偶数个结点。

在此之外，我们注意到如果路径的开头存在连续两个 (，那么可以在上面来回走来刷左括号；如果路径的结尾存在两个 )，那么可以在上面来回走来刷右括号。

那么一个初步的想法就是：

• 如果 \(x\) 可以直接沿着左右括号交替的路径走到 \(y\)，那就做完了。
• 否则，从 \(x\) 沿着交替的左右括号一直走，走到某一个 ((，然后开始刷足够多的左括号，然后原路返回 \(x\)，再从 \(x\) 沿着某条经过偶数个结点的路径走到 \(y\)，从 \(y\) 沿着交替的左右括号一直走，走到某一个 ))，然后开始刷右括号，刷到与剩下的左括号平衡，然后返回 \(y\)​ 即可。

第一种情况正确性显然。

第二种情况，三段路径中每段路径经过的点数都是偶数，且前面刷了足够多的左括号让中间的段的每个右括号都能匹配，且最后能够刷右括号去抵消之前刷多了的左括号，所以也是正确的。

那么如果这两种情况都不满足，说明从 \(x\) 沿着左右交替的括号无法走到 \(y\) 也无法走到 ((，只能走到 ))，那这样显然不合法。

所以思路想完了，现在考虑如何实现。

• 第一步，我们要先判断 \(x\) 到 \(y\)​ 是否至少有一条路径经过偶数个结点。

  1. 如果图是二分图，那么只需要判断 \(x, y\) 是否不在同一部。

  2. 如果图不是二分图，那么说明图中一定存在奇环，那么可以在这个奇环上绕一圈来控制奇偶性，这样任意两点 \(x, y\) 之间一定有经过偶数个结点偶数的路径。

• 第二步，我们要判断 \(x\) 是否能通过交替的左右括号走到 \(y\)。

  这个我们只需要保留原图中从 ( 连向 ) 的边，然后使用并查集判断 \(x, y\) 是否在同一个连通块即可。

• 第三步，我们要判断 \(x\) 是否能通过交替的左右括号走到某一个 ((。

  这个我们只需要在第二步的图中把 (( 的两个括号所在的连通块打个标记即可。

• 第四步，我们要判断 \(y\) 是否能通过交替的左右括号走到某一个 ))

  这个跟第三步同理。

注意这题并不保证图联通，还要额外判一下连通性，然后就完结撒花了。

Code

#include <bits/stdc++.h>

using namespace std;

#define SZ(x) ((int)((x).size()))
#define lb(x) ((x) & (-(x)))
#define bp(x) __builtin_popcount(x)
#define bpll(x) __builtin_popcountll(x)
#define mkp make_pair
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<double, int> pdi;

const int MAXN = 5e5 + 10;

struct Dsu {
    vector<int> fa;
    void init(int n) {
        fa.resize(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            fa[i] = i;
        }
    }
    int fifa(int x) {
        if (fa[x] == x) {
            return x;
        }
        return fa[x] = fifa(fa[x]);
    }
    void merge(int x, int y) {
        x = fifa(x);
        y = fifa(y);
        if (x != y) {
            fa[x] = y;
        }
    }
};

int n, m, q;
string s;
vector<int> G[MAXN];

void solve() {
    cin >> n >> m >> q >> s;
    s = ' ' + s;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    int cnt_id = 0;
    vector cop_id(n + 1, 0);
    auto dfs_cop = [&](auto&& self, int u) -> void {
        cop_id[u] = cnt_id;
        for (auto v : G[u]) {
            if (cop_id[v]) {
                continue;
            }
            self(self, v);
        }
    };
    for (int i = 1; i <= n; i++) {
        if (!cop_id[i]) {
            cnt_id++;
            dfs_cop(dfs_cop, i);
        }
    }

    vector is_erfen(n + 1, true);
    vector clr(n + 1, -1);
    auto dfs_clr = [&](auto&& self, int u, int idx) -> void {
        if (!is_erfen[idx]) {
            return ;
        }
        for (auto v : G[u]) {
            if (clr[v] == -1) {
                clr[v] = !clr[u];
                self(self, v, idx);
            } else if (clr[v] == clr[u]) {
                is_erfen[idx] = false;
                break;
            }
        }
    };
    for (int i = 1; i <= n; i++) {
        if (clr[i] == -1) {
            clr[i] = 0;
            dfs_clr(dfs_clr, i, cop_id[i]);
        }
    }

    Dsu dsu;
    dsu.init(n);
    for (int u = 1; u <= n; u++) {
        for (auto v : G[u]) {
            if (s[u] != s[v]) {
                dsu.merge(u, v);
            }
        }
    }
    vector flgl(n + 1, false), flgr(n + 1, false);
    for (int u = 1; u <= n; u++) {
        for (auto v : G[u]) {
            if (s[u] == '(' && s[v] == '(') {
                flgl[dsu.fifa(u)] = true;
                flgl[dsu.fifa(v)] = true;
            }
            if (s[u] == ')' && s[v] == ')') {
                flgr[dsu.fifa(u)] = true;
                flgr[dsu.fifa(v)] = true;
            }
        }
    }

    string ans;
    while (q--) {
        int x, y;
        cin >> x >> y;

        if (cop_id[x] != cop_id[y]) {
            ans += '0';
            continue;
        }
        int id = cop_id[x];
        if (is_erfen[id] && clr[x] == clr[y]) {
            ans += '0';
            continue;
        }
        if (s[x] != '(' || s[y] != ')') {
            ans += '0';
            continue;
        }

        if (dsu.fifa(x) == dsu.fifa(y)) {
            ans += '1';
            continue;
        }
        if (flgl[dsu.fifa(x)] && flgr[dsu.fifa(y)]) {
            ans += '1';
            continue;
        }
        ans += '0';
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    while (T--) solve();
    return 0;
}